package com.apkcore.bl;

public class _11盛最多水的容器 {

    public int maxArea3(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (left < right) {
            int minH = Math.min(height[left], height[right]);
            max = Math.max(max, minH * (right - left));
            while (left < right && height[left] <= minH) {
                left++;
            }
            while (left < right && height[right] <= minH) {
                right--;
            }
        }
        return max;
    }

    /**
     * 双指针解法，area = (minH)*(r-l)
     * 在这个基础上去重，如果左指针指向的值移动后是小于等于前面的值，那么可以不必重复计算，因为肯定是小于已求的最大值的
     * 同理右指针也一样
     */
    public int maxArea2(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (left < right) {
            if (height[left] <= height[right]) {
                int minH = height[left];
                max = Math.max(max, minH * (right - left));
                while (left < right && height[left] <= minH) {
                    left++;
                }
            } else {
                int minH = height[right];
                max = Math.max(max, minH * (right - left));
                while (left < right && height[right] <= minH) {
                    right--;
                }
            }
        }
        return max;
    }

    /**
     * 在上面的基础上进行优化
     * 其实这个优化实际意义不大
     */
    public int maxArea1(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (left < right) {
            int minH = (height[left] <= height[right]) ? height[left++] : height[right--];
            max = Math.max(max, minH * (right - left + 1));
        }
        return max;
    }

    /**
     * 双指针解法，area = (minH)*(r-l)
     */
    public int maxArea0(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (left < right) {
            if (height[left] <= height[right]) {
                max = Math.max(max, height[left] * (right - left));
                left++;
            } else {
                max = Math.max(max, height[right] * (right - left));
                right--;
            }
        }
        return max;
    }
}
